public class T5二叉树的最近公共祖先 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode nodeL = new TreeNode(2);
        TreeNode nodeR = new TreeNode(3);
        root.left = nodeL;
        root.right = nodeR;
        TreeNode ret = lowestCommonAncestor(root,nodeL,nodeR);
        System.out.println(ret.val);
    }

    public static TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) {
        //出口
        if (root == q || root == p || root == null) return root;

        TreeNode left = lowestCommonAncestor(root.left,p,q);//左边找
        TreeNode right = lowestCommonAncestor(root.right,p,q);//右边找

        //三种情况
        //1.两边都找到了
        if(left != null && right != null) return root;
        //2.找到一边
        if (left != null && right == null) return left;
        if (right != null && left == null) return right;
        //3.都没找到
        return null;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}